剑指Offer 39. 二叉树的深度
解答1[Java]:递归
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public int TreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = TreeDepth(root.left);
int rightDepth = TreeDepth(root.right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
}
递归的另一种写法
class Solution {
public int maxDepth(TreeNode root) {
if(root == null)
return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
}
}
解答2[Java]:非递归
核心思想
层次遍历。
代码
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
public int TreeDepth(TreeNode root) {
if(root == null)
return 0;
int deep = 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int start = 0, end = 1;
while(!queue.isEmpty()){
TreeNode node = queue.poll();
start ++;
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
if(start == end){
end = queue.size();
start = 0;
deep ++;
}
}
return deep;
}
}
层次遍历的另一种写法:双循环
public class Solution {
public int treeDepth2(BinaryTreeNode root) {
if (root == null)
return 0;
BinaryTreeNode current = null;
LinkedList<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
queue.offer(root);
int cur, last;
int level = 0;
while (!queue.isEmpty()) {
cur = 0;//记录本层已经遍历的节点个数
last = queue.size();//当遍历完当前层以后,队列里元素全是下一层的元素,队列的长度是这一层的节点的个数
while (cur < last)//当还没有遍历到本层最后一个节点时循环
{
current = queue.poll();//出队一个元素
cur++;
//把当前节点的左右节点入队(如果存在的话)
if (current.left != null) {
queue.offer(current.left);
}
if (current.right != null) {
queue.offer(current.right);
}
}
level++;//每遍历完一层level+1
}
return level;
}
}